#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// G_type matrix
typedef vector<vector<int> > G_type;
inline bool reachable(int val){return val!=0;}
bool find_alternative(const G_type& g, vector<int>& link, vector<int>& used, int s, bool inmatch=false)// in the same time reverse the path
{
	int e_got=-1;
	for(int e=0;e<g.size();e++)
	{
		if(!reachable(g[s][e])) continue;
		if(!used[e]) { e_got=e; break; }
		else if( (link[s]==e) != inmatch
			&& find_alternative(g, link, used, e, !inmatch))
		{
			e_got=e; break;
		}
	}
	if(e_got!=-1) // fine, get the path, reverse the path
	{
		if(link[s]!=e_got)
		{
			link[s]=e_got;
			link[e_got]=s;
		}
		used[s]=used[e_got]=1;
		return true;
	}
	return false;
}
void bipartite_match(G_type g, vector<int>& link)
{
	int N=g.size();
	fill(link.begin(), link.end(), -1);
	vector<int> used(N, 0);
	for(int i=0;i<N;i++)
	{
		if(!used[i])
			find_alternative(g, link, used, i);
	}
}

// test
G_type gen_g(int N)
{
	G_type g(N);
	for(int i=0;i<N;i++)
		g[i].resize(N);
	return g;
}
void LN(G_type& g, int i, int j)
{
	g[i][j]=g[j][i]=1;
}
int main()
{
	{
		// test correctness
		G_type g=gen_g(20);
		for(int r=0;r<100;r++)
		{
			int i=rand()%g.size();
			int j=rand()%g.size();
			if((i+j)%2==1)
				LN(g, i, j);
		}

		// the same algo like bipartite match
		int N=g.size();
		vector<int> link(N);

		fill(link.begin(), link.end(), -1);
		vector<int> used(N, 0);
		for(int i=0;i<N;i++)
		{
			if(!used[i])
				find_alternative(g, link, used, i);
		}

		// this time it should return "false" for all find_argment
		for(int i=0;i<N;i++)
		{
			if(!used[i])
				assert(!find_alternative(g, link, used, i));
		}
	}
	//{
	//	G_type g=gen_g(6);
	//	LN(g, 0,3);
	//	LN(g, 0,4);
	//	LN(g, 1,4);
	//	LN(g, 1,5);
	//	LN(g, 2,5);
	//	
	//	vector<int> link(6);
	//	bipartite_match(g, link); // 0,3; 1,4; 2,5;
	//}
	//{
	//	G_type g=gen_g(6);
	//	LN(g, 0,3);
	//	LN(g, 1,3);
	//	LN(g, 2,3);
	//	LN(g, 2,5);

	//	vector<int> link(6);
	//	bipartite_match(g, link); // 0,3; 2,5;
	//}
	//{
	//	G_type g=gen_g(6);// (0,1,2,3), (4,5)
	//	LN(g,0,4);
	//	LN(g,1,4);
	//	LN(g,2,5);
	//	LN(g,3,5);
	//	
	//	vector<int> link(6);
	//	bipartite_match(g, link); // two
	//}	
	return 0;
}